package com.chj.chuji.tijie08;

import java.util.Comparator;
import java.util.PriorityQueue;

public class FruitMerger {
	public static class NodeComparator implements Comparator<Integer> {
		@Override
		public int compare(Integer o1, Integer o2) {
			if (o1 > o2) {
				return 1;
			} else if (o1 < o2) {
				return -1;
			}
			return 0;
		}
	}

	public static void main(String[] args) {
		int n = 3;
		PriorityQueue<Integer> heap = new PriorityQueue<>(new NodeComparator());

		int[] aa = new int[] { 1, 2, 9 };
		for (int i = 0; i < n; i++) {
			heap.add(aa[i]);
		}

		int x, y;/// 优先级队列中前面两最小值
		int res = 0;
		for (int i = 0; i < n - 1; i++) {
			x = heap.peek();
			heap.poll();
			y = heap.peek();
			heap.poll();
			res += (x + y);
			heap.add(x + y);
		}

		System.out.println(res);
	}

}

//	#include<bits/stdc++.h>
//	using namespace std;
//
//int main()
//{
//    int n;
//    while(cin >> n)
//    {
//        priority_queue<int, vector<int>, greater<int> > p;///小根堆
//        int num;
//        for(int i = 0; i < n; i ++)
//        {
//            cin >> num;
//            p.push(num);
//
//        }
//        int x,y;///优先级队列中前面两最小值
//        int res = 0;
//        for(int i = 0; i < n - 1; i ++)
//        {
//            x = p.top();
//            p.pop();
//            y = p.top();
//            p.pop();
//            res += (x + y);
//            p.push(x + y);
//
//        }
//        cout << res << endl;
//    }
//    return 0;
//}
